#include <vector>
#include <list>
#include <string>
#include <algorithm>
template<typename HashedObj>
class HashTable{
private:
	std::vector<std::list<HashedObj> > theLists;
	int currentSize; 
	//int nextPrime(int n);
	void rehash(){
		std::vector<std::list<HashedObj> > oldLists = theLists; 
		theLists.resize(nextPrime(2*theLists.size()));
		for(int j=0; j<theLists.size();j++)
			theLists.clear();
		for (int i = 0; i<oldLists.size(); i++){
			typename std::list<HashedObj>::iterator itr = oldLists[i].begin();
			while(itr != oldLists.end())
				insert(*itr++);
		}
	}
	int myhash(const HashedObj& x)const{
		int hashVal = hash(x); 
		hashVal %= theLists.size();
		if(hashVal < 0){
			hashVal += theLists.size();
			
		}
	}	

public:
	explicit HashTable(int size=101);

	bool contains(const HashedObj& x)const{
		const std::list<HashedObj> &whichList = theLists[myhash(x)];
		return std::find(whichList.begin(),whichList.end(),x) != whichList.end();
	}
	bool insert(const HashedObj& x){
		std::list<HashedObj>& whichList = theLists[myhash(x)];
		typename std::list<HashedObj>::iterator it; 
		it = find(whichList.begin(),
				whichList.end(),x);
		if(it == whichList.end()){
			return false;
		}
		
		currentSize++;
		if(currentSize > theLists.size()){
			rehash();
		}
		return true;
		
	}
	void remove(const HashedObj& x){
		std::list<HashedObj>& whichList = theLists[myhash(x)];
		typename std::list<HashedObj>::iterator it = find(
				whichList.begin(),
				whichList.end(),
				x);
		if(it == whichList.end()){
			return false; 
		}
		else{
			whichList.erase(it);
			--currentSize;
			return true;
		}
	}
	void makeEmpty(){
		for(int i =0; i<theLists.size(); i++){
			theLists[i].clear();
		}
	}

};
